package problem.year2023.month04

import kotlin.math.max


/**
 * @author LiangMu
 * @version $Id: Day26.java, v 0.1 2023年04月27日 14:55 LiangMu Exp $$
 */
class Day26 {
    /**
     * 给你一个整数数组 nums 和两个整数 firstLen 和 secondLen，请你找出并返回两个非重叠 子数组 中元素的最大和，长度分别为 firstLen 和 secondLen 。
     *
     * 长度为 firstLen 的子数组可以出现在长为 secondLen 的子数组之前或之后，但二者必须是不重叠的。
     *
     * 子数组是数组的一个 连续 部分。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
     * 输出：20
     * 解释：子数组的一种选择中，[9] 长度为 1，[6,5] 长度为 2。
     * 示例 2：
     *
     * 输入：nums = [3,8,1,3,2,1,8,9,0], firstLen = 3, secondLen = 2
     * 输出：29
     * 解释：子数组的一种选择中，[3,8,1] 长度为 3，[8,9] 长度为 2。
     * 示例 3：
     *
     * 输入：nums = [2,1,5,6,0,9,5,0,3,8], firstLen = 4, secondLen = 3
     * 输出：31
     * 解释：子数组的一种选择中，[5,6,0,9] 长度为 4，[0,3,8] 长度为 3。
     *  
     *
     * 提示：
     *
     * 1 <= firstLen, secondLen <= 1000
     * 2 <= firstLen + secondLen <= 1000
     * firstLen + secondLen <= nums.length <= 1000
     * 0 <= nums[i] <= 1000
     */
    fun maxSumTwoNoOverlap(nums: IntArray, firstLen: Int, secondLen: Int): Int {
        return max(maxSumTwo(nums, firstLen, secondLen), maxSumTwo(nums, secondLen, firstLen))
    }


    /**
     * 判断数组中的最大和
     *
     * @param nums 数组
     * @param firstLen 左边数组的大小
     * @param secondLen 右边的数组的大小
     */
    fun maxSumTwo(nums: IntArray, firstLen: Int, secondLen: Int): Int {
        if (nums.size == firstLen + secondLen) return nums.sum()
        var left = 0;
        var res = 0;
        for (index in nums.indices) {
            if (index < firstLen) {
                left += nums[index]
            }
            // 更新区间范围
            var right = 0
            if (index >= firstLen) {
                left = max(left, left - nums[index - firstLen] + nums[index])
                // 向右遍历，找second len 中最大值
                var temp = 0
                for (index2 in index until nums.size) {
                    if (index2 - index <= secondLen) {
                        temp += nums[index2]
                    } else {
                        temp = temp - nums[index2 - secondLen] + nums[index2]
                    }
                    right = max(right, temp)
                }
            }
            res = max(res, left + right)
        }
        return 0
    }
}
